package leetcode.剑指offer.后40;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/8/1 21:56
 * @description：https://leetcode-cn.com/problems/chou-shu-lcof/
 */
public class 剑指_49_丑数 {
    @Test
    public void test() {
        Solution solution = new Solution();
    }

    class Solution {
        public int nthUglyNumber(int n) {
            int[] dp = new int[n + 1];
            dp[1] = 1;
            int dp2 = 1, dp3 = 1, dp5 = 1;
            for (int i = 2; i <= n; i++) {
                int num2 = dp[dp2] * 2;
                int num3 = dp[dp3] * 3;
                int num5 = dp[dp5] * 5;
                dp[i] = Math.min(Math.min(num2, num3), num5);
                if (dp[i] == num2) dp2++;
                if (dp[i] == num3) dp3++;
                if (dp[i] == num5) dp5++;
            }
            return dp[n];
        }
    }
}
